package com.study.algorithm.basicalsort.imp;

import com.study.algorithm.basicalsort.BasicalSort;
import com.study.algorithm.utils.ListUtil;

import java.util.List;

import static com.study.algorithm.utils.ListUtil.DeepClone;


/**
 * 快速排序
 * 原理：（以从小到大排序为例）
 * 第一步：找到一个基准值，通过左找比他小的值，找到交换位置，然后右找比他大的值，找到交换位置
 * 第二步：循环第一步直到找到该基准值的最终位置
 * 第三步：以该基准值最终位置为分隔点，分隔成三段（自己单独占据一个段）
 * 第四步：将其余两段，重复第一二三步，最终每个点都找到自己最终位置，排序结束
 */
public class QuickSortImpl implements BasicalSort {
    @Override
    public List<Integer> basicalSort(List<Integer> originList) {
        int size = originList.size();
        List<Integer> destList = DeepClone(originList);
        if (size <= 1) {
            return destList;
        }

        partionQuickSort(destList, 0, size - 1);
        return destList;
    }


    private void partionQuickSort(List<Integer> list, int startIndex, int endIndex) {
        //取第一个值为基准值（不同基准值，直接影响效率，但是这个值需要根据实际估测）
        int privot = list.get(startIndex);
        int currPrivotIndex = startIndex;
        int leftFindIndex = endIndex;
        int rightFindIndex = startIndex;
        boolean isLeftForCurrFindDirection = true;
        while (leftFindIndex != rightFindIndex) {
            int findIndex = rightFindIndex;
            if (isLeftForCurrFindDirection) {
                findIndex = leftFindLowerPosition(list, rightFindIndex, leftFindIndex, privot);
                findIndex = findIndex == -1 ? currPrivotIndex : findIndex;
                leftFindIndex = findIndex;
            }
            if (!isLeftForCurrFindDirection) {
                findIndex = rightFindBiggerPosition(list, rightFindIndex, leftFindIndex, privot);
                findIndex = findIndex == -1 ? currPrivotIndex : findIndex;
                rightFindIndex = findIndex;
            }
            ListUtil.ExchangeValue(list, currPrivotIndex, findIndex);
            isLeftForCurrFindDirection = !isLeftForCurrFindDirection;
            currPrivotIndex = findIndex;
        }
        if (currPrivotIndex > startIndex) {
            partionQuickSort(list, startIndex, currPrivotIndex - 1);
        }
        if (currPrivotIndex < endIndex) {
            partionQuickSort(list, currPrivotIndex + 1, endIndex);
        }

    }


    private int rightFindBiggerPosition(List<Integer> list, int startIndex, int endIndex, int privot) {
        int findIndex = -1;
        if (startIndex > endIndex) {
            //todo:异常
            throw new ArrayIndexOutOfBoundsException("数组越界");
        }
        for (int currIndex = startIndex; currIndex <= endIndex; currIndex++) {
            int currVal = list.get(currIndex);
            if (currVal > privot) {
                findIndex = currIndex;
                break;
            }
        }
        return findIndex;
    }

    private int leftFindLowerPosition(List<Integer> list, int startIndex, int endIndex, int privot) {
        int findIndex = -1;
        if (startIndex > endIndex) {
            //todo:异常
            //todo:异常
            throw new ArrayIndexOutOfBoundsException("数组越界");
        }
        for (int currIndex = endIndex; currIndex >= startIndex; currIndex--) {
            int currVal = list.get(currIndex);
            if (currVal < privot) {
                findIndex = currIndex;
                break;
            }
        }

        return findIndex;
    }
}
